package fun.ticsmyc.question;

/**
 * 1601. 最多可达成的换楼请求数目
 *
 * 对可能的结果进行枚举。  枚举过程时间复杂度O(2^n) ， 对每次枚举进行判断 O(n)  整体O(m*2^n)
 * @author Ticsmyc
 * 2022/2/28 12:17
 **/
public class 二进制枚举 {


    public int maximumRequests(int n, int[][] requests) {
        int m  = requests.length;
        int res =0;

        //共 2^m种情况
        for(int i=0;i<(1<<m);++i){
            //数一下i里有几个1
            int cnt = getCnt(i);
            if(cnt >res && check(requests,i)){
                res = cnt;
            }
        }
        return res;
    }

    private boolean check(int[][] requests, int cur){
        int[] cnt = new int[20];
        int sum =0;
        for(int i=0;i<16;++i){
            if(((cur>>i)&1)==1){
                //这个要换
                int from = requests[i][0];
                int to = requests[i][1];
                if(++cnt[from] == 1) sum++;
                if(--cnt[to] ==0) sum--;
            }
        }
        return sum==0;
    }

    private int getCnt(int i) {
        int cnt=0;
        while( i !=0 ){
            i = i&(i-1);
            cnt++;
        }
        return cnt;
    }
}
